//You are given an integer array nums and an integer target. 
//
// You want to build an expression out of nums by adding one of the symbols '+' 
//and '-' before each integer in nums and then concatenate all the integers. 
//
// 
// For example, if nums = [2, 1], you can add a '+' before 2 and a '-' before 1 
//and concatenate them to build the expression "+2-1". 
// 
//
// Return the number of different expressions that you can build, which evaluate
//s to target. 
//
// 
// Example 1: 
//
// 
//Input: nums = [1,1,1,1,1], target = 3
//Output: 5
//Explanation: There are 5 ways to assign symbols to make the sum of nums be tar
//get 3.
//-1 + 1 + 1 + 1 + 1 = 3
//+1 - 1 + 1 + 1 + 1 = 3
//+1 + 1 - 1 + 1 + 1 = 3
//+1 + 1 + 1 - 1 + 1 = 3
//+1 + 1 + 1 + 1 - 1 = 3
// 
//
// Example 2: 
//
// 
//Input: nums = [1], target = 1
//Output: 1
// 
//
// 
// Constraints: 
//
// 
// 1 <= nums.length <= 20 
// 0 <= nums[i] <= 1000 
// 0 <= sum(nums[i]) <= 1000 
// -1000 <= target <= 1000 
// 
// Related Topics 深度优先搜索 动态规划 
// 👍 749 👎 0


package leetcode.editor.cn;

import org.junit.Assert;

//Java：Target Sum
class P494TargetSum {
    public static void main(String[] args) {
        Solution solution = new P494TargetSum().new Solution();
        // TO TEST
        Assert.assertEquals(solution.findTargetSumWays(new int[]{1, 1, 1, 1, 1}, 3),
                5);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        int count = 0;
        int[] memo;
//        f(1)=f(2-1)+f(0+1)
//        public int findTargetSumWays(int[] nums, int target) {
//            int[] arr = new int[nums.length];
//
//        }


        public int findTargetSumWaysDFS(int[] nums, int target) {
            findTargetSumWays(nums, 0, target);

            return count;
        }

        private void findTargetSumWays(int[] nums, int start, int target) {
            if (start == nums.length && target == 0) {
                count++;
            }
            if (start == nums.length) {
                return;
            }
            findTargetSumWays(nums, start + 1, target - nums[start]);
            findTargetSumWays(nums, start + 1, target + nums[start]);

        }
        public int findTargetSumWays(int[] nums, int target) {
            int sum = 0;
            for (int num : nums) {
                sum += num;
            }
            int diff = sum - target;
            if (diff < 0 || diff % 2 != 0) {
                return 0;
            }
            int n = nums.length, neg = diff / 2;
            int[][] dp = new int[n + 1][neg + 1];
            dp[0][0] = 1;
            for (int i = 1; i <= n; i++) {
                int num = nums[i - 1];
                for (int j = 0; j <= neg; j++) {
                    dp[i][j] = dp[i - 1][j];
                    if (j >= num) {
                        dp[i][j] += dp[i - 1][j - num];
                    }
                }
            }
            return dp[n][neg];
        }

        public int findTargetSumWaysD(int[] nums, int target) {
            int sum = 0;
            for (int num : nums) {
                sum += num;
            }
            int diff = sum - target;
            if (diff < 0 || diff % 2 != 0) {
                return 0;
            }
            int neg = diff / 2;
            int[] dp = new int[neg + 1];
            dp[0] = 1;
            for (int num : nums) {
                for (int j = neg; j >= num; j--) {
                    dp[j] += dp[j - num];
                }
            }
            return dp[neg];
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}